Gramatyka kategorialna

Gramatyka kategorialna – rodzaj gramatyki formalnej, w której wyróżnia się: słownik będący zbiorem atomów języka opisywanego przez gramatykę, typizację początkową określającą zasady przypisywania typów elementom ze słownika oraz typ naczelny gramatyki. Teoria gramatyk kategorialnych zajmuje się zatem różnymi metodami opisu języków symbolicznych i języka naturalnego, opartymi na typizacji języka.

Podstawowe zasady

1. Zasada funktorowości – wyrażenia złożone języka składają się z pewnej części głównej (funktora) oraz części uzupełniającej (argumentów). Dla przykładu, w wyrażeniu Wojtek widzi słonia wyraz widzi jest funktorem, zaś argumentami wyrazy Wojtek i słonia.
2. Zasada typizacji – kategorię syntaktyczną wyrażenia określa przyporządkowany temu wyrażeniu typ.
3. Zasada atomiczności – typ wyrażenia złożonego jest funkcją typów wyrażeń atomowych wchodzących w skład tego wyrażenia.
4. Zasada zastępowalności – dwa wyrażenia należą do tej samej kategorii wtedy i tylko wtedy, gdy każde poprawnie zbudowane wyrażenie, zawierające jedno z nich, nie przestaje być poprawnie zbudowanym wyrażeniem (nie zmienia swojej kategorii) po zastąpieniu jednego przez drugie. Kategorią syntaktyczną będziemy nazywać zbiór wyrażeń wzajemnie zastępowalnych z zachowaniem poprawności gramatycznej. Przykładowo, wyrazy słonia i bażanta należą do jednej kategorii syntaktycznej, gdyż zawsze możemy zastąpić jeden z tych wyrazów drugim bez utraty poprawności syntaktycznej (np. Wojtek widzi słonia $\to$ Wojtek widzi bażanta).

Definicje pomocnicze

Struktury i języki funktorowe

Niech FS(V) oznacza zbiór wszystkich struktur funktorowych nad V. FS(V) określamy jako najmniejszy zbiór spełniający następujące warunki:

1. V ∈ FS(V),
2. jeżeli A₁,...,A_n ∈ FS(V), gdzie n≥2, to (A₁...A_n)_i ∈ FS(V), dla każdego 1≤i≤n,

gdzie zbiór V jest zbiorem atomów.

Dowolny zbiór struktur funktorowych nad V nazywamy językiem funktorowym nad V.

Typy i typizacje

Ustalmy przeliczalny, nieskończony zbiór stałych Pr, którego elementy nazywamy typami pierwotnymi. Określamy: Tp = FS(Pr). Elementy zbioru Tp nazywamy typami (typy spoza Pr nazywamy typami funktorowymi).

Definicja intuicyjna

Typizacja polega na przyporządkowaniu wyrażeniu funktorowemu pewnego zbioru typów, będącego podzbiorem zbioru typów powstałego ze zbioru typów pierwotnych oraz typów funktorowych.

Typizacją zbioru FS(V) nazywamy dowolną funkcję T określoną na FS(V), która każdej strukturze A ∈ FS(V) przyporządkowuje pewien zbiór T(A) ⊆ Tp (T(A) może być pusty).

Dla dowolnej typizacji T na FS(V) określamy:

• TYP(T) = {x ∈ Tp: x ∈ T(A), dla pewnego A ∈ FS(V)}.

Typizację T nazywamy skończoną jeżeli zbiór TYP(T) jest skończony, a jednoznaczną – jeżeli dla każdej

Definicja intuicyjna

Zbiór TYP(T) – zbiór typów, które dana typizacja może przyporządkować pewnej strukturze funktorowej A.

struktury A ∈ FS(V) zbiór T(A) zawiera najwyżej jeden typ; piszemy wówczas: T(A) = x zamiast: x ∈ T(A).

Klasyczne gramatyki kategorialne (w sensie Leśniewskiego – Ajdukiewicza – Bar-Hillela) – formalna definicja

Gramatyka kategorialna to trójka G = (V_G, I_G, s_G), taka że:

• V_G jest zbiorem atomów,
• I_G jest typizacją na FS(V_G), dla której I_G(A) = Ø, jeśli A ∈ V_G, s_G ∈ Pr.

V_G, I_G, s_G nazywamy kolejno: słownikiem, typizacją początkową i typem naczelnym gramatyki G.

Przykład

Język L_A jest to język złożony z poprawnie zbudowanych równości arytmetycznych; zbiór atomów języka L_A jest sumą zbioru N_A będącego zbiorem nazw liczb naturalnych i zbioru {+,·,=}. Zbiór termów języka L_A (TER_A) jest najmniejszym zbiorem spełniającym następujące warunki:

• N_A ⊆ TER_A,
• Jeżeli A, B ∈ TER_A to (A + B)₂ (A · B)₂ ∈ TER_A.

Do języka L_A należą też struktury postaci (A = B)₂, gdzie A, B ∈ TER_A.

Strukturom z L_A przypisujemy typ s, strukturom z TER_A – typ n. Symbole + i · są funktorami języka które w połączeniu z dwiema strukturami typu n (symbol + lub · umieszczamy pomiędzy struktury typu n) tworzą nową strukturę typu n – otrzymują zatem typ (nnn)₂. Symbol = umieszczony pomiędzy strukturami typu n tworzy strukturę typu s – otrzymuje typ (nsn)₂.

Gramatyką kategorialną (w sensie Leśniewskiego – Ajdukiewicza – Bar-Hillela) określającą język L_A jest gramatyka G postaci: G = (V_A, I_A, s), gdzie:

• V_A = N_A,
• I_A(v) = n, dla v ∈ N_A; I_A(+) = I_A(·) = (nnn)₂; I_A(=) = (nsn)₂.

Znaczenia i zastosowanie gramatyk kategorialnych

I logika

• analiza roli typów w składni i semantyce języka

II lingwistyka

• ustanowienie wzorca formalizacji języka
• maszynowa analiza syntaktyczna
• przekład maszynowy

Bibliografia

• Wojciech Buszkowski, Logiczne podstawy gramatyk kategorialnych Ajdukiewicza-Lambeka, Wydawnictwo PWN, Warszawa 1989, ISBN 83-01-08319-0.